Suppose that a graph is realized from a stochastic block model where one ofthe blocks is of interest, but many or all of the vertices' block labels areunobserved. The task is to order the vertices with unobserved block labels intoa ``nomination list'' such that, with high probability, vertices from theinteresting block are concentrated near the list's beginning. We proposeseveral vertex nomination schemes. Our basic - but principled - setting anddevelopment yields a best nomination scheme (which is a Bayes-Optimalanalogue), and also a likelihood maximization nomination scheme that ispractical to implement when there are a thousand vertices, and which isempirically near-optimal when the number of vertices is small enough to allowcomparison to the best nomination scheme. We then illustrate the robustness ofthe likelihood maximization nomination scheme to the modeling challengesinherent in real data, using examples which include a social network involvinghuman trafficking, the Enron Graph, a worm brain connectome and a politicalblog network.
展开▼
